package com.sx.sx1.lintcode.day717;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class LC376 {

     static class TreeNode {
      public int val;
     public TreeNode left, right;
      public TreeNode(int val) {
          this.val = val;
          this.left = this.right = null;
      }

}

    static class Solution {
        /**
         * @param root: the root of binary tree
         * @param target: An integer
         * @return: all valid paths
         *          we will sort your return value in output
         */
        public List<List<Integer>> binaryTreePathSum(TreeNode root, int target) {
            //二叉树路径相关问题很多可以用中序遍历解决
            List<List<Integer>> ans = new ArrayList<>();
            if(root ==null) return ans;
            Stack<TreeNode> stk = new Stack<>();
            List<Integer> path = new ArrayList<>();
            TreeNode pre =null;
            int pathsum =0;
            while (!stk.isEmpty() || root!=null){
                while (root!=null){
                    stk.add(root);
                    path.add(root.val);
                    pathsum+= root.val;
                    root = root.left;
                }

                root = stk.peek();
                if(root.left ==null && root.right ==null){
                    if(pathsum == target){
                        ans.add(new ArrayList<>(path));
                    }
                }

                if(root.right ==null || root.right ==pre){
                    root = stk.pop();
                    int delnum = path.get(path.size()-1);
                    path.remove(path.size()-1);
                    pathsum -=delnum;
                    pre =root;
                    root =null;
                }else{
                    root = root.right;
                }
            }
            return ans;
        }
    }


    public static void main(String[] args) {
        Solution s = new Solution();
        TreeNode t = new TreeNode(1);
        t.left = new TreeNode(2);
        t.right = new TreeNode(4);
        t.left.left = new TreeNode(2);
        t.left.right = new TreeNode(3);

        System.out.println(s.binaryTreePathSum(t,5));
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有199条未读消息，请及时查看
376 · 二叉树的路径和
算法
简单
通过率
32%

题目
题解55
笔记
讨论99+
排名
记录
描述
给定一个二叉树，找出所有路径中各节点相加总和等于给定 目标值 的路径。

一个有效的路径，指的是从根节点到叶节点的路径。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


样例
样例1:

输入:
{1,2,4,2,3}
5
输出: [[1, 2, 2],[1, 4]]
说明:
这棵树如下图所示：
	     1
	    / \
	   2   4
	  / \
	 2   3
对于目标总和为5，很显然1 + 2 + 2 = 1 + 4 = 5
样例2:

输入:
{1,2,4,2,3}
3
输出: []
说明:
这棵树如下图所示：
	     1
	    / \
	   2   4
	  / \
	 2   3
注意到题目要求我们寻找从根节点到叶子节点的路径。
1 + 2 + 2 = 5, 1 + 2 + 3 = 6, 1 + 4 = 5
这里没有合法的路径满足和等于3.
标签
相关题目

246
二叉树的路径和 II
中等

472
二叉树的路径和 III
困难

863
二叉树的路径和IV
中等

1353
根节点到叶节点求和
中等
推荐课程

简历/BQ/项目 面试软技能指导
FLAG高级工程师深度BQ辅导，简历打造+1V1模拟面试，反面试套路、高效上岸！
357/1856
已开启智能提示
发起考试
15 分 00 秒
1234567891011121314151617181920212223
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
…        // write your code here
    }
}
控制台
历史提交

 */